1. Field of the Invention
The present invention relates to packet routing in telecommunication systems, and, more particularly, to determining paths through nodes of a packet network for routing of packets with guaranteed service levels.
2. Description of the Related Art
In interconnected communications packet networks, such as the Internet, users establish connections between a source and a destination with a stream of data packets, called packet flows, that are transferred through the network over a network path. The network path is defined by a set of nodes interconnected by a set of links. Packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. At the highest levels, packet networks with high capacity that route packets transferred between other, outside packet networks are commonly referred to as xe2x80x9cbackbonexe2x80x9d networks. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the backbone network.
FIG. 1 shows a backbone network 100 of the prior art having nodes N1-N9 interconnected through links 101 that allow communication between packet networks 102-104. An ingress point is a router of node N1 that transfers packets to the backbone network 100 from a source (packet network 102), and an egress point is a router of node N4 that transfers packets from the backbone network 100 to a destination (packet network 104). The backbone network 100 may support an interior routing protocol to distribute network topology information and route packets between ingress and egress points based on best effort routing (e.g., destination-based shortest path) through the nodes N1-N9. A centralized network management system 105 may be employed to 1) provision virtual circuits, or packet flows, through the backbone network 100; 2) monitor capacity and utilization of links 101; and 3) coordinate calculation and installation of provisioned paths. Forwarding tables are used by each node""s router to forward each received packet to the next node toward its destination. In addition, the centralized network management system 105 may also be employed to collect and distribute network topology information.
Interior routing protocols are employed by routers to determine forwarding of packets between a source and destination pair along a path through the nodes of the interconnected packet network. Packets received by a node""s router are forwarded to other nodes based on a forwarding table constructed in accordance with the interior routing protocol or routes installed with explicit route provisioning. Interior routing protocols may also specify exchange network topology and link-state information (xe2x80x9cnetwork topology informationxe2x80x9d) among routers to allow the node""s router to construct the corresponding forwarding table. An example of a widely-used interior routing protocol for xe2x80x9cbest effortxe2x80x9d routing is the Open Shortest Path First (OSPF) protocol. In addition, some routing protocols associate a link xe2x80x9ccostxe2x80x9d with each link between nodes. This link cost may be associated with, for example, average link utilization or revenue generated by the link, as well as link importance in the network. When link-state information or link-bandwidth (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network""s topology.
Since routing of packets at the higher levels is desirably performed at high speed, each higher-level packet network may use its own interior routing protocol in addition to the interior routing protocol of the lower-level packet network. Routing protocols, in addition to providing connectivity, may also enable traffic management. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols in backbone networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) with provisioned service levels (also known as guaranteed quality-of-service (QoS)).
Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the backbone network. This path having a guaranteed level of service between ingress and egress points may be referred to as a Network Tunnel Path (NTP). As would be apparent to one skilled in the art, specific implementations of NTPs exist for different types of networks. As examples of NTPs, virtual circuits may be established for packet flows in TCP/IP networks, virtual circuits may be established for cells in Asynchronous Transfer Mode (ATM) networks, and label switched paths (LSPs) may be established for packets in MPLS networks. Packets of a signaling protocol, such as RSVP (Reservation Protocol for IP and MPLS networks) or LDP (Label Distribution Protocol for MPLS networks), may be used to reserve link bandwidth and establish an NTP, once routing for the NTP is calculated. NTPs may be provisioned as an explicit route along specific paths between nodes of the backbone network (i.e., when an NTP is provisioned, all intermediate points may be specified through which a packet passes between the ingress and egress points of the NTP).
In MPLS networks, packets are encapsulated by appending to the packet, or forming from the packet, additional information when the packet is received at an ingress point. The additional information, called a label, is used by routers of the backbone network to forward the packets. FIG. 2 shows such an encapsulated packet 200 having a label 201 appended to packet 202. The label summarizes information in the packet header. The summary may be based on the header field and include an origination (source) address field (o) 210 identifying the address of the ingress point, a termination (destination) address field (t) 211 identifying the address of the egress point(s). In some cases, the label may simply be a pointer that identifies or is otherwise related to specific origination and termination address fields in the header of the received packet. The label also includes one or more service level fields (bd) 212. Service level field 212 may identify a desired service level for the virtual circuit (called a xe2x80x9cdemandxe2x80x9d), such as minimum bandwidth required. In some networks, the service level field is implied from the label itself. Other fields 213 may be included in the label 201, such as MPLS standard version, interior routing protocol version, maximum delay, or other types of service level parameters. The label 201 may alternatively be inserted into the packet header (PH) 214 of the packet 202, so the order of fields shown in FIG. 2 is exemplary only. Backbone networks may employ labels to group encapsulated packets having similar LSPs into classes (equivalence classes), and methods for forwarding equivalence classes may be employed to simplify calculation of routing for LSPs.
To generate a forwarding table, each router computes a set of preferred paths through the network nodes, and may use the weights to calculate the set of preferred paths. Each preferred path has a minimum total weight between nodes as well as minimum summed weight through nodes of the path, which is known in the art as shortest-path routing. This set of preferred paths may be defined with a shortest-path tree (SPT). The forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet to its destination along the shortest path of the SPT. The SPT may be calculated using an algorithm such as Dijkstra""s algorithm, described in E. Dijkstra, xe2x80x9cA Note: Two Problems In Connection With Graphs,xe2x80x9d Numerical Mathematics, vol.1, 1959, pp. 269-271.
A common shortest-path routing algorithm employed by routers to generate routing of an LSP is the min-hop algorithm. In the min-hop algorithm, each router calculates a path through the backbone network for the stream of packets (packet flows) between the ingress and egress point. Each router constructs a path for routing the packet flow from the ingress point to the egress point with the least number (xe2x80x9cminxe2x80x9d) of feasible links (xe2x80x9chopsxe2x80x9d) (a feasible link is a link that exists and has sufficient capacity to route the packet flow). Routing schemes of the prior art, such as shortest-path routing, forward packets based only on destination addresses and use only static and traffic-characteristic-independent link weights to calculate paths for routing tables. Some links on the shortest path between certain pairs of ingress and egress points may be congested while other links on alternate paths are under-utilized.
A signaling mechanism, such as RSVP or LDP, may be employed to both reserve and establish a connection through the network for a packet flow. The signaling mechanism may specify quality-of-service attributes for the LSP traversing the backbone network. Link congestion caused by shortest-path routing of multiple LSPs by shortest path routing may cause rejection of reservation requests by signaling mechanisms, even though sufficient levels of service (quality of service guarantees) for the LSP may have existed in alternate, under-utilized paths that are only slightly longer. Available network resources are not efficiently utilized when shortest-path routing is employed.
In accordance with embodiments of the present invention, data is routed along paths through a network of nodes interconnected by links and having a plurality of ingress-egress point pairs. Routing data along paths includes receiving a request for a path with a service demand for routing data between one of the ingress-egress point pairs of the network. A subnetwork of nodes and links is defined from the network based on the service demand. A set of weights is defined for the links of the subnetwork taking into account impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network. A shortest path through the subnetwork is determined in accordance with the set of weights for the links, the shortest path being the path with the service demand between the one of the ingress-egress point pairs of the network.
For some exemplary embodiments, the routing method determines a preferred path for a new network tunnel path (NTP) request. The preferred path is defined between a pair of ingress and egress points through the nodes of a packet network and maintains provisioned and requested levels of Quality of Service (QoS). The preferred path through the nodes is selected so as to reduce impact to service levels of paths of other currently provisioned NTPs passing through each particular node that is selected for the preferred path. The routing method determines the preferred path based on shortest path routing through a subnetwork derived from the network topology, the subnetwork defined with link weights determined from critical links. The critical links are links identified based on remaining bandwidth on the links, position in the network relative to ingress-egress point pairs, and a criterion for generally maintaining relatively high QoS or other service levels over all paths between ingress-egress point pairs. Generally, the routing method maintains relatively high service levels (e.g., bandwidth) available in existing paths for future NTP requests between all pairs of ingress and egress points in the network after routing the new NTP request.